package leetcode;

/*
107. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class problems_107 {

    public static void main(String[] arge) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(2);
        TreeNode A4 = new TreeNode(3);
        TreeNode A5 = new TreeNode(4);
        TreeNode A6 = new TreeNode(4);
        TreeNode A7 = new TreeNode(3);
        A1.left = A2;
        A1.right = A3;
        A2.left = A4;
        A2.right = A5;
        A3.left = A6;
        A3.right = A7;
        List<List<Integer>> ret = new Solution().levelOrderBottom(A1);
        System.out.println(ret);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        List<List<Integer>> ret = new ArrayList<>();
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            if(null == root) return ret;
            bfs(root, 0);
            Collections.reverse(ret);
            return ret;
        }
        private void bfs(TreeNode node, int index) {
            if(null != node.left) bfs(node.left, index + 1);
            if(null != node.right) bfs(node.right, index + 1);
            // 追加用
            while (ret.size() <= index){
                ret.add(new ArrayList<>());
            }
            ret.get(index).add(node.val);
        }
    }
}
